Linked list random node [Reservoir Sampling]

Time: O(N); Space: O(1); medium

Given a singly linked list, return a random node’s value from the linked list.

Each node must have the same probability of being chosen.

Follow up:

  1. What if the linked list is extremely large and its length is unknown to you?

  2. Could you solve this efficiently without using extra space?

Example 1:

# Init a singly linked list [1,2,3].

head = ListNode(1)

head.next = ListNode(2)

head.next.next = ListNode(3)

solution = Solution(head)

# getRandom() should return either 1, 2, or 3 randomly.

# Each element should have equal probability of returning.

solution.getRandom()

[1]:

class ListNode(object):
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

[2]:

from random import randint

class Solution1(object):

    def __init__(self, head):
        """
        head - the linked list's head.
        Note that the head is guanranteed to be not null, so it contains at least one node.
        :type head: ListNode
        """
        self.__head = head

    # Proof of Reservoir Sampling:
    # https://discuss.leetcode.com/topic/53753/brief-explanation-for-reservoir-sampling
    def getRandom(self):
        """
        Returns a random node's value.
        :rtype: int
        """
        reservoir = -1
        curr, n = self.__head, 0
        while curr:
            reservoir = curr.val if randint(1, n+1) == 1 else reservoir
            curr, n = curr.next, n + 1
        return reservoir

[3]:

head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)

s = Solution1(head)
assert s.getRandom() == 1 or 2 or 3